Resumen de algoritmos para torneos de programación

Andrés Mejía

27 de febrero de 2008

Índice

1. Teoría de números 1 1.1. Big mod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Criba de Eratóstenes . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. Programación dinámica 2 2.1. Longest common subsequence . . . . . . . . . . . . . . . . . . . . 2

Listings

1. Big mod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Big mod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3. Longest common subsequence . . . . . . . . . . . . . . . . . . . . 2

1. Teoría de números

1.1. Big mod

Listing 1: Big mod

1 // retorna ( bˆ p )mod(m)
// 0 <= b , p <= 2147483647
3 // 1 <= m <= 46340
long f ( long b , long p , long m){
5 long mask = 1 ;
long pow2 = b %m;
7 long r = 1 ;
9 while ( mask ){
i f (p & mask )
11  r = ( r ∗ pow2 ) %m;
pow2 = ( pow2∗pow2 ) %m;
13  mask <<= 1 ;

}

15 return r ;

}

1.2. Criba de Eratóstenes

Marca los números primos en un arreglo. Algunos tiempos de ejecución:

SIZE  Tiempo (s)
100000  0.004
1000000  0.078
10000000  1.550
100000000  14.319

Listing 2: Big mod

#include <iostream>

2

const int SIZE = 1000000;

4

// c r i b a [ i ] = f a l s e s i i es primo
6 bool c r i b a [ SIZE +1];
8 void buildCriba ( ) {
memset ( criba , false , sizeof ( c r i b a ) ) ;

10

c r i b a [ 0 ] = c r i b a [ 1 ] = true ;
12 for ( int i =2; i<=SIZE ; i += 2){
c r i b a [ i ] = true ;
14 }
16 for ( int i =3; i<=SIZE ; i += 2){
i f ( ! c r i b a [ i ] ) {
18  for ( int j=i+i ; j<=SIZE ; j += i ){
c r i b a [ j ] = true ;
20  }
}
22 }

}

2. Programación dinámica

2.1. Longest common subsequence

Listing 3: Longest common subsequence

1 #define MAX( a , b) ( ( a>b ) ? ( a ) : ( b ) )
int dp [ 1 0 0 1 ] [ 1 0 0 1 ] ;

3

int l c s ( const s t r i n g &s , const s t r i n g &t ){
5 int m = s . s i z e ( ) , n = t . s i z e ( ) ;

i f (m = 0 | | n = 0) return 0 ;
7 for ( int i =0; i<=m; ++i )
dp [ i ] [ 0 ] = 0 ;
9 for ( int j =1; j<=n ; ++j )
dp [ 0 ] [ j ] = 0 ;
11 for ( int i =0; i<m; ++i )
for ( int j =0; j<n ; ++j )
13  i f ( s [ i ] = t [ j ] )
dp [ i +1][ j +1] = dp [ i ] [ j ]+1;
15  else
dp [ i +1][ j +1] = MAX( dp [ i +1][ j ] , dp [ i ] [ j +1]);
17 return dp [m] [ n ] ;

}